COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	~[CαGEOMETRIC MODELING THEORY.
C00004 00003	[1.1	Kinds of Geometric Models.]
C00006 00004		For a naive start,  first consider a  3-D array in which each
C00010 00005		
C00013 00006
C00016 00007		
C00019 00008
C00022 00009
C00024 00010	~FC1.2	Polyhedron Definitions.
C00028 00011	~FC1.3	Camera, Light and Image Modeling.
C00035 ENDMK
C⊗;
~[C;αGEOMETRIC MODELING THEORY.;
λ30;I425,0;P5;JCFA             SECTION 1.
~JCFD                  GEOMETRIC MODELING THEORY.
~I950,0;JUFA
[1.0	Introduction to Geometric Modeling.]

	In  the specific  context of  computer  vision and  graphics,
geometric modeling refers to constructing computer representations of
physical objects,    cameras,   images  and  light for  the  sake  of
simulating their  behavior. In  Artificial Intelligence,  a geometric
model is  a kind of world model; ignoring subtleties, geometric world
modeling is distinguished from semantic and logical world modeling in
that  it is quantitative  and numerical  rather than  qualitative and
symbolic.  The  notion of a  world model requires  an external  world
environment to be modeled,  an internal  computer environment to hold
the  model,   and a  task performing  entity  to use  the model.   In
geometry,  modeling is a synthetic problem,  like a construction with
ruler  and straight  edge, modeling  problems require  an algorithmic
solution  rather than a  proof. The adjective  "geometric" however is
quite apropos  in that it  literally means  "world measure" which  is
exactly the activity to be automated.
~Q;F.
[1.1	Kinds of Geometric Models.]

	The main  problem  of geometric  modeling is  to invent  good
methods for representing  arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid,   opaque,
Newtonian and macroscopic with a mathematically well behaved surface.
Physical objects  include: the earth, chairs, roads,  and plastic toy
horses.  Physical objects may be  moved about in space,
but two objects  can not simultaneously occupy the  same space at the
same time.  The scope of the problem can be appreciated by  examining
the virtues and drawbacks of the kinds of models listed in box 1.1 below.
~|------------------------------------------λ10;JAFA
BOX 1.1~JCFA   TEN KINDS OF GEOMETRIC MODELS.
~↓F.
Space Oriented:
	1. 3-D Space Array.
	2. Recursive Cells.
	3. 3-D Density Function.
	4. 2-D Surface Functions.
	5. Parametric Surface Functions.
~↑W640;F.
Object Oriented:
	6. Manifolds.
	7. Polyhedra.
	8. Volume Elements.
	9. Cross Sections.
 	10. Skeletons.
~|---------------------------------------λ30;JUFA

	For a naive start,  first consider a  3-D array in which each
element indicates  the presence or absence of  solid matter in a cube
of space.  Such a 3-D  space array has the very desirible  properties
of "spatial addressing" and "spatial uniqueness" in their most direct
and  natural form. Spatial addressing refers  to finding out what the
model  contains  within a  distance  R  of  a  locus  X,Y,Z;  spatial
uniqueness refers  to modeling the property that  physical solids can
not occupy the same space. The  main drawback of the 3-D space  array
model is illustrated by the apparently legal FORTRAN statement:
~JC;F.DIMENSION SPACE(10000,10000,10000)
	The  problem with  such  a  dimension  statement is  that  no
present  day  computer memory  is  large enough  to  contain  a 10↑15
element  array. Smaller  space  arrays  arrays  can  be  useful  but
necessarily  can not  model  large volumes  with  high resolution.  A
further drawback of space arrays is that objects and surfaces are not
readily accessible  as  entities; that  is a  space  array lacks  the
desirible property of "object coherence".

	The space array  idea can be salvaged because  large portions
of the  array contain similar values. By  grouping blocks of elements
with the same values together,   the addressing process becomes  more
complicated but  the overall memory  required is reduced and  the two
desired  properties can be  maintained. One way of  doing this (which
has been  discovered in several  applications) is "recursive  cells";
the  whole space  is considered to  be a  cell; if  the space  is not
homogeneous than  the first  cell is  divided into  two (or  four  or
eight) sub cells and  the criterion is applied again.  This technique
of recursive  celling allows the spatial sorting  of objects,  if the
object models can be subdivided at each recursion without  losing the
properties of the objects.
	
	In  mathematical physics,    arbitrary physical  objects  are
frequently  referred   to  as  three  dimensional  density  functions
W=RHO(X,Y,Z). Unfortunately such density functions can not be written
out for  objects such as  a typing chair  or a plastic  horse without
resorting  to a programming language or  an extensive table (which is
equivalent to the space  array model).  Some special  objects however
are essentially  2-D and can be  approximated by surface  funtion Z =
F(X,Y). For example geodetic  maps are handled by computer  in
such a fashion.

	By definition, a function is  single valued; consequently the
description of even modestly complicated objects can not be expressed
directly  as  a  single  function  of  orthogonal  rectilinear  space
coordinates X,   Y and Z. It is necessary  either to adopt parametric
functions  or  to subdivide  the  object  into portions  that  can be
described by  simple  functions of  Cartesian  variables. The  latter
course  of subdividing objects  into portions is  called segmentation
and is discussed later; the former  course can be illustrated by  the
example in figure **  showing (X,Y,Z) locus of the surface  of a unit
cube  expressed  as  functions of  (U,V)  surface  coordinates.   The
advantage of parametric  functions is  that extended arbitrary  curve
surfaces  can  be  expressed;  some of  the  disadvantages  are  that
parametric  curves may be  self intersecting,   they are  not easy to
modified locally,   and  the functions  become impractically  complex
before interesting objects are achieved.

	In  passing from  space oriented  models  to object  oriented
models, I  wish to point out the  mysterious dichotomy between objects
and the space that  contains the objects,  and observe that the  same
dichotomy appears in the foundations of  physics.  However,  our goal
is  merely  to simulate  the properties  of  objects; rather  than to
explain them.   In  this regard,    the representation  of time  will
receive  no special attention;  although an advanced  problem solving
robot will want to run  world simulations along multiple time  paths,
the present  discussion will be  restricted to simulations  along one
time path.

	After  existence in space and  time, another general property
of physical objects is that they  can be enclosed by an unbroken  two
dimensional surface  with an  unabiguous inside  and outside.   Which
touchs upon the mathematical topic (celebrated in song by Tom Lehrer)
of  the  algebraic  topology  of  locally  Euclidean  transitions  of
infinitely differentiable  oriented Riemann manifolds.  A manifold is
the mathematical abstraction of a  surface; a Riemann manifold has  a
metric function; an oriented manifold has a unambiguous inside and an
outside; the phrase  "infinitely differentiable" can be taken to mean
that the surface  is smooth and continuous;  and the phrase  "locally
Euclidean transitions" refers to the process of segmenting the object
into   portions  that  can  be   approximated  by  relatively  simple
functions. In particular,  the 2-D Riemann  (sub)manifold embedded in
3-D Euclidean space is  the mathematical object that comes closest to
representing the  shape  and extent  of  the surface  of  a  physical
object; such  manifolds  lead directly  to the  topology of  surfaces
which in turn is a convenient computational approach to polyhedra.
	
	The topology of a  2-D Riemann submanifold embedded in  a 3-D
Euclidean space is  composed of three kinds of simplex: the 0-Simplex
(or  vertex), the  1-Simplex  (or  edge),    and  the  2-Simplex  (or
triangle). In topological analysis,  it may be demonstrated that such
2-D Riemann submanifolds may be divided into simplex such that Eulers
equations  F-E+V=2-2*H  is  satisfied  (where  F  is  the  number  of
2-simplex,   E  is  the number  of 1-simplex,    V is  the  number of
0-simplex and H is  the genus (number of  handles) of the  manifold);
and such  that the  surface of  the manifold  can be approximated  by
local  functions over  each 2-simplex which  are Euclidean  and which
splice  together  correctly  at  all  the  1-simplex  (edges).     By
introducing  a  sufficient  (but  finite)  number  of  triangles  the
manifold  can  be  approximated to  within  an  epsilon,  by constant
functions; yielding the geometric object called the "polyhedron".

	The main  inherent advantage  of  a polyhedral  model is  its
coherent  surface topology of  faces,   edges and  vertices.   Such a
surface can  be  subdivided  without  losing  its  coherence  or  the
coherence of the object.  The disadvantages  of polyhedra include the
lack  of  spatial uniqueness  and  spatial  addressing; necessitating
computation to be done to detect and prevent spatial conflict  and to
find the  portions of an  entity occupying  a given volume.   Another
disadvantage  is  that  polyhedra per  se  are  not  curved surfaces,
however by associating an appropriate function with each face a model
of  a 2-D Riemann  manifold can be  made,   which is a  curved object
representation. 

	Returning  to  the  survey, arbitrary  objects  can  also  be
described  by listing a set  of cross sections taken  at a sufficient
number of cutting planes; this is  how the shape of a ship's hull  or
an airplane's wing is specified.  Cross sections have the interesting
feature  of good  space modeling  on one  axis.   Forsaking arbitrary
shaped objects,  large classes of things can be described in terms of
a  small set  of basic  volume elements.   For  example,  Roberts and
others have built  models of familar  objects using only  rectangular
and triangular right prisms. Although,  arbitrary solid polyhedra can
be  constructed out of  tetrahedrons (the  3-simplex); no significant
modeling system exists using this potentially interesting approach.

	Skeletal models  are based on  abstracting an  object into  a
stick figure and  by associating a diameter or set  of cross sections
with the sticks. In particular,  spine cross section models have been
pursued at Stanford  by (Agin,  Binford  and Nervatia; Blum).   Spine
cross section models have the advantage of being able to express many
objects in a concise  form suitable for  recognition,  however  spine
cross section models can  not be used directly for  arbitrary shapes.
Finally,   it is useful to represent physical  objects by a very weak
model such as by using sets of spheres or sets of surface  points. It
is  interesting  to  note  that  the  "reality"  that  the  robot  in
Winograd's  thesis could talk about,   was a blocks  world based on a
geometric model consisting only of  points, size of block, and  a two
page LISP subroutine named FINDSPACE.

	To the best of  my knowledge, this survey is  complete; as of
this year, 1974,  there are no other significantly different kinds of
simple geometric models. The desirable properties that have turned up
in this  survey are included in  the list below. The  final desirable
property is  that there be some hope that the computer can derive the
model by measurements it can make itself, although it is quite likely
that one model will be  best for input and another model will be best
for simulation.

~|---------------------------------------------------------------λ10;JAFA
BOX 1.2	DESIRABLE PROPERTIES FOR A GEOMETRIC MODEL.

	1. Spatial Addressing.
	2. Spatial Uniqueness.
	3. Object Coherence with Divisibility.
	4. Surface Coherence with Divisibility.
	5. Shape generality.
	6. Large Extent with High Resolution.
	7. Readily Modifiable.
	8. Suitable for photometric, kinematic and dynamic simulation.
	9. Feasible memory and computation requirements.
       10. Potential for automatic model acquistion.
~|--------------------------------------------------------------λ30;JUFA

	Meta modeling ideas
prototype/instance and parts structure.
~FC1.2	Polyhedron Definitions.
~JUFA
	There are essentially three kinds of {polyhedron} definition:
topological, geometrical and algebraic. 
Each definition emphases  a different aspect  of the  concept so
that in simple forms the  definitions  fall  short  of  being
equivalent.

	Topologically, the  surface elements of  a polyhedron  forms a
graph that  satisfies Euler's F-E+V=2-2*H equation; where  F, E and V
are the number of faces,   edges and vertices of the polyhedron;  and
where  H is  the number  of holes  in (or  genus of)  the polyhedron.
However,  not  all  Eulerian  graphs  of  faces,  edges and  vertices
correspond to solid polyhedra.

	Geometrically,   a polyhedron  is a  simply connected  finite
region  of space composed of  the union of a  finite number of convex
polyhedra. A  convex polyhedron  is a  non  empty, simply  connected,
finite region  of space enclosed by  a finite number of  planes.  The
boundary  of  the  polyhedron  is called  its  surface.    The simply
connected regions  of the  surface belonging  to only  one plane  are
called faces.  The simply connected regions of  the surface belonging
to exactly two planes are called  edges; and the loci of the  surface
where three or more planes interect are called vertices.

~|---------------------------------------------------------------λ10;JAFA
BOX 1.3	Properties of a Solid Polyhedron:

	1. [EULERIAN]. Satisfies Eulers Equation F-E+V=2*B-2*H
	2. [TRIVALENCE]. All vertices and faces have three or more edges.
	3. [NON-SELF-INTERSECTION]. No edge intersects a face or vertex
		to which it is not topologically linked.
	4. [FACE PLANARITY]. All the vertices of a face are coplanar.
	5. [SIMPLY CONNECTED SOLIDITY]. The volume measure is finite and positive.
	6. [FACE CONVEXITY]. All the faces are convex.
	7. [FACE SIMPLY CONNECTED PERIMETER].
~|---------------------------------------------------------------λ30;JUFA
~FC1.3	Camera, Light and Image Modeling.
~JUFA
	Common to both computer graphics and  vision is the necessity
to  model  cameras,    light  and  images  so  that pictures  may  be
synthesized or  analysized.  The reader  completely naive  to  camera
modeling is  emphatically warned that  all camera discussion  in this
paper  refers to a logical camera geometry  rather than to a physical
camera geometry, the difference is illustrated in figure **.
The basic camera model that I use has eight degrees of freedom: three
in location, three in orientation and two in projection.

	LOCATION:	CX, CY, CZ	vector to camera lens center.
	ORIENTATION:	WX, WY, WZ	Orientation vector.
	PROJECTION:	AR, FR		Aspect Ratio and Focal Ration.

	The light scattering  properties of ordinary surfaces  can be
modeled  by thinking  of  the surface  as composed  of  many
little mirrors. The  orientation of each mirror  is described by  two
angles,  its tilt  from the normal vector of the  surface and its pan
about the  normal vector with respect to a specified reference vector
in the tangent plane of the surface. For a perfect reflecting surface
all the differential mirrors have  a zero pan and tilt; for isotropic
conventional   surfaces   the   statistical   distribution   of   pan
orientations is flat and  the distribution of tilt orientations  is a
blip function; and  for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.